package com.cube.algorithms.heuristic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author litb
 * @since 2025/6/24 19:49
 * 使用延迟接受爬山法 (Late Acceptance Hill-Climbing, LAHC) 启发式算法解决旅行商问题 (TSP) 的示例。
 */

public class TspLahcExample {

    /**
     * 程序主入口，用于演示算法效果。
     *
     * @param args 命令行参数（未使用）
     */
    public static void main(String[] args) {
        // 创建一个城市列表用于测试
        List<City> cities = new ArrayList<>();
        cities.add(new City("北京", 116.46, 39.92));
        cities.add(new City("上海", 121.48, 31.22));
        cities.add(new City("广州", 113.23, 23.16));
        cities.add(new City("深圳", 114.07, 22.62));
        cities.add(new City("成都", 104.06, 30.67));
        cities.add(new City("杭州", 120.19, 30.26));
        cities.add(new City("西安", 108.95, 34.27));
        cities.add(new City("武汉", 114.31, 30.52));

        // 创建算法实例并执行
        TspLahcExample solver = new TspLahcExample();
        // 设置LAHC参数：历史列表长度，最大迭代次数
        Tour resultTour = solver.findTour(cities, 50, 100);

        // 打印结果
        System.out.println("LAHC算法找到的路径:");
        String pathString = resultTour.getPath().stream()
                .map(City::getName)
                .collect(Collectors.joining(" -> "));
        System.out.println(pathString);
        System.out.printf("总距离: %.2f%n", resultTour.getTotalDistance());

        System.out.println("\n注意: 此解是启发式算法给出的近似最优解。每次运行结果可能因随机性而不同。");
    }

    /**
     * 核心方法：使用LAHC算法寻找最优路径。
     *
     * @param cities        城市列表
     * @param historyLength 成本历史列表的长度 (L)
     * @param maxIterations 最大迭代次数
     * @return 最终找到的最优路径（Tour对象）
     */
    public Tour findTour(List<City> cities, int historyLength, int maxIterations) {
        // 1. 初始化
        if (cities.isEmpty()) {
            return new Tour(Collections.emptyList(), 0);
        }

        // 创建一个初始解：随机打乱城市顺序
        List<City> currentSolution = new ArrayList<>(cities);
        Collections.shuffle(currentSolution);
        double currentDistance = calculateTotalDistance(currentSolution);

        // 初始化最优解为当前解
        List<City> bestSolution = new ArrayList<>(currentSolution);
        double bestDistance = currentDistance;

        // 创建并初始化历史成本列表
        double[] costHistory = new double[historyLength];
        Arrays.fill(costHistory, currentDistance);

        // 2. 迭代搜索
        for (int v = 0; v < maxIterations; v++) {
            // 产生一个新的邻近解 (2-opt swap)
            List<City> newSolution = generateNeighbor(new ArrayList<>(currentSolution));
            double newDistance = calculateTotalDistance(newSolution);

            // 获取历史成本索引 (循环使用)
            int historyIndex = v % historyLength;

            // LAHC核心接受准则:
            // 1. 如果新解比当前解更好 (贪心部分)
            // 2. 或者，如果新解比L次迭代前的历史解更好 (延迟接受部分)
            // 满足任意一个条件，则接受新解
            if (newDistance < currentDistance || newDistance < costHistory[historyIndex]) {
                currentSolution = newSolution;
                currentDistance = newDistance;
            }

            // 如果当前解优于已知的全局最优解，则更新全局最优解
            if (currentDistance < bestDistance) {
                bestSolution = new ArrayList<>(currentSolution);
                bestDistance = currentDistance;
            }

            // 无论新解是否被接受，都用本次迭代结束时采纳的解的成本来更新历史列表
            // 这确保了历史列表记录的是每个时间点的"当前成本"
            costHistory[historyIndex] = currentDistance;
        }

        return new Tour(bestSolution, bestDistance);
    }

    /**
     * 计算一个路径的总距离。
     *
     * @param tour 城市路径列表
     * @return 总距离
     */
    private double calculateTotalDistance(List<City> tour) {
        double totalDistance = 0.0;
        for (int i = 0; i < tour.size() - 1; i++) {
            totalDistance += tour.get(i).distanceTo(tour.get(i + 1));
        }
        // 不要忘记加上从最后一个城市回到起点的距离
        if (!tour.isEmpty()) {
            totalDistance += tour.get(tour.size() - 1).distanceTo(tour.get(0));
        }
        return totalDistance;
    }

    /**
     * 产生一个邻近解。
     * 这里采用简单的"2-opt"思想的变体：随机交换路径中两个城市的位置。
     *
     * @param tour 当前路径
     * @return 一个新的路径
     */
    private List<City> generateNeighbor(List<City> tour) {
        if (tour.size() < 2) {
            return tour;
        }
        // 随机选择两个不同的位置
        int pos1 = (int) (tour.size() * Math.random());
        int pos2 = (int) (tour.size() * Math.random());
        while (pos1 == pos2) {
            pos2 = (int) (tour.size() * Math.random());
        }

        // 交换这两个位置的城市
        Collections.swap(tour, pos1, pos2);
        return tour;
    }


    /**
     * 内部类，用于表示一个城市。
     * 从TspHeuristicExample中复用，保持一致性。
     */
    public static class City {
        private final String name;
        private final double x;
        private final double y;

        public City(String name, double x, double y) {
            this.name = name;
            this.x = x;
            this.y = y;
        }

        public String getName() {
            return name;
        }

        public double distanceTo(City other) {
            double deltaX = this.x - other.x;
            double deltaY = this.y - other.y;
            return Math.sqrt(deltaX * deltaX + deltaY * deltaY);
        }

        @Override
        public String toString() {
            return name;
        }
    }

    /**
     * 用于封装TSP问题解的内部类。
     * 包含路径和总距离。
     */
    public static class Tour {
        private final List<City> path;
        private final double totalDistance;

        public Tour(List<City> path, double totalDistance) {
            // 为了显示闭环，将起点添加到路径末尾
            List<City> finalPath = new ArrayList<>(path);
            if (!finalPath.isEmpty()) {
                finalPath.add(finalPath.get(0));
            }
            this.path = finalPath;
            this.totalDistance = totalDistance;
        }

        public List<City> getPath() {
            return path;
        }

        public double getTotalDistance() {
            return totalDistance;
        }
    }
} 